import collections
from typing import List


class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        quantity.sort()
        count = [num for num in collections.Counter(nums).values() if num >= quantity[0]]
        count.sort()

        if sum(count) < sum(quantity):
            return False
        if count[-1] < quantity[-1]:
            return False

        size1 = len(quantity)
        size2 = len(count)

        def dfs(i, vals):
            if i == size1:
                return True
            for j in range(size2):
                if quantity[i] <= vals[j]:
                    vals[j] -= quantity[i]
                    if dfs(i + 1, vals):
                        return True
                    vals[j] += quantity[i]
            return False

        return dfs(0, count)


if __name__ == "__main__":
    print(Solution().canDistribute(nums=[1, 2, 3, 4], quantity=[2]))  # False
    print(Solution().canDistribute(nums=[1, 2, 3, 3], quantity=[2]))  # True
    print(Solution().canDistribute(nums=[1, 1, 2, 2], quantity=[2, 2]))  # True
    print(Solution().canDistribute(nums=[1, 1, 2, 3], quantity=[2, 2]))  # False
    print(Solution().canDistribute(nums=[1, 1, 1, 1, 1], quantity=[2, 3]))  # True
